0% completed
In this lesson, we will explore three different approaches to solving dynamic programming problems with more complex examples:
- Memoization (Top-down approach)
- Top-down DP with Explicit Recursion
- Bottom-up DP (Tabulation)
1. Solving a Problem with Memoization
Problem: Calculate the number of unique paths from the top-left corner to the bottom-right corner of an m x n grid. You can only move right or down.
Time Complexity for Unique Paths Using Memoization
- Recursive Calls:
- The function
findPathsis called recursively to compute the number of unique paths to each cell in them x ngrid. - Number of Unique States: Each state is defined by a unique
(row, col)combination, and there aresuch unique states in the grid. - Number of Recursive Calls:
- Each unique state is computed only once, as we use memoization. This prevents redundant recursive calls and ensures each state is solved once.
- Overall Time Complexity:
- The function
Space Complexity for Unique Paths Using Memoization
-
Memoization Map (
memo):- The
memomap stores results for each unique state(row, col), so it has space complexity. - The size of the
Stringkeys is insignificant compared to the number of entries, so this does not impact the space complexity significantly.
- The
-
Recursive Call Stack:
- Maximum Depth:
- The maximum depth of the recursive call stack is
in the worst case, representing the diagonal traversal of the grid from (m-1, n-1)to(0, 0).
- The maximum depth of the recursive call stack is
- Maximum Depth:
-
Overall Space Complexity:
- The total space complexity accounts for both the memoization map and the call stack depth:
, for storing results, plus for the recursion stack.
- The total space complexity accounts for both the memoization map and the call stack depth:
2. Solving a Problem with Top-Down DP
Problem: Calculate the minimum cost to climb a staircase where each step has a certain cost associated with it. You can climb one or two steps at a time.
Time Complexity for Minimum Cost Climbing Stairs Using Top-Down DP
- Recursive Calls:
- The function
findMinCostis called recursively to compute the minimum cost for each stepi. - Number of Unique Subproblems:
- Each index from
0ton-1(wherenis the length of thecostarray) represents a unique subproblem. - Since each subproblem is computed only once due to memoization, the total number of recursive calls is
.
- Each index from
- The function
- Key Operations:
- Base Case Checks:
- The checks
if (i < 0),if (i == 0 || i == 1), andif (dp[i] != -1)run in.
- The checks
- Recursive Calculations:
- For each call to
findMinCost, two recursive calls are made (findMinCost(cost, i - 1)andfindMinCost(cost, i - 2)), but due to memoization, each index is only processed once.
- For each call to
- Filling and Returning Values:
- Storing and returning values in
dp[i]take.
- Storing and returning values in
- Base Case Checks:
Overall Time Complexity:
- Each index
ifrom0ton-1is processed once, leading to a total time complexity of:
Space Complexity for Minimum Cost Climbing Stairs Using Top-Down DP
-
DP Array (
dp):- The
dparray is used to store precomputed results for each index from0ton-1, takingspace.
- The
-
Recursive Call Stack:
- Maximum Depth of Recursion:
- The maximum depth of the recursion is
, which occurs when the function is called starting from the highest index down to 0.
- The maximum depth of the recursion is
- Space Complexity for Call Stack:
The space used by the recursion stack can go up to
in the worst case. - Maximum Depth of Recursion:
3. Solving a Problem with Bottom-Up DP
Problem: Find the length of the longest palindromic subsequence in a given string.
Time Complexity for Longest Palindromic Subsequence Using Bottom-Up DP
-
Initialization:
- Single Character Initialization:
- The
forloop that setsdp[i][i] = 1for eachirunstimes, where nis the length of the input strings.
- The
- Single Character Initialization:
-
Nested Loops:
- The outer loop runs
times, as it iterates over lengths of substrings starting from 2 up to n. - The middle loop runs
times for each length, as it starts from the beginning of the string up to n - len. - The inner loop computes the value at
dp[i][j], where, and runs operations for each combination.
- The outer loop runs
-
Overall Time Complexity:
- The number of operations for filling the
dptable isbecause each of the cells in the upper triangle of the 2D array is filled once. - Total Time Complexity:
- The number of operations for filling the
Space Complexity for Longest Palindromic Subsequence Using Bottom-Up DP
-
DP Table (
dp):- The 2D
dptable has a size of, where nis the length of the input strings. - Space used by
dp:
- The 2D
-
Auxiliary Space:
- The algorithm does not use any additional data structures that grow with the input size.
- Overall auxiliary space:
.
Overall Space Complexity:
- The total space complexity is:
On this page
- Solving a Problem with Memoization
Time Complexity for Unique Paths Using Memoization
Space Complexity for Unique Paths Using Memoization
- Solving a Problem with Top-Down DP
Time Complexity for Minimum Cost Climbing Stairs Using Top-Down DP
Space Complexity for Minimum Cost Climbing Stairs Using Top-Down DP
- Solving a Problem with Bottom-Up DP
Time Complexity for Longest Palindromic Subsequence Using Bottom-Up DP
Space Complexity for Longest Palindromic Subsequence Using Bottom-Up DP